package demo1;

/**
 * @Author liangzai
 * @Description:
 */
public class Training {
    public int minOperations(int[] nums, int k) {
        int res = 0; long sum;
        Heap h = new Heap(nums, k);
        while (h.size > 1) {
            sum = h.poll() * 2 + h.poll();
            if (sum < k) {
                h.offer(sum);
            }
            res++;
        }
        return res + h.size;
    }
}

class Heap {
    long[] heap;
    int size;
    Heap(int[] a, int k) {
        heap = new long[a.length];
        for (int n : a) {
            if (n < k) {
                heap[size++] = n;
            }
        }
        for (int i = size / 2; i >= 0; i--) {
            heapify(i);
        }
    }
    void heapify(int i) {
        int l = 2 * i + 1, r = 2 * i + 2, min = i;
        if (l < size && heap[l] < heap[min]) {
            min = l;
        }
        if (r < size && heap[r] < heap[min]) {
            min = r;
        }
        if (min != i) {
            long temp = heap[i];
            heap[i] = heap[min];
            heap[min] = temp;
            heapify(min);
        }
    }
    long poll() {
        long res = heap[0];
        heap[0] = heap[--size];
        heapify(0);
        return res;
    }
    void offer(long val) {
        heap[size++] = val;
        for (int i = size - 1; i > 0; ) {
            int p = (i - 1) / 2;
            if (heap[p] > heap[i]) {
                long temp = heap[p];
                heap[p] = heap[i];
                heap[i] = temp;
                i = p;
            } else {
                break;
            }
        }
    }

    public ListNode mergeNodes(ListNode head) {
        ListNode pre = head, curr = pre.next;
        while(curr != null){
            while(curr.val != 0){
                pre.val += curr.val;
                curr = curr.next;
            }
            pre.next = curr.next == null ? null : curr;
            pre = pre.next;
            curr = curr.next;
        }
        return head;
    }
}
